package com.gofaraway.service.student.左神算法课.v2;


/**
 * 归并排序
 *
 * @author ChenPeng
 * @date 2025/5/8 17:34
 */
public class Code03_MergeSort {

    public void mergeSort(int[] arr) {

        if (arr == null || arr.length == 0) {
            return;
        }
        //有一个process函数 这个函数的功能是 给定一个数组 和这个数组的左右边界 这个函数可以将这数组排好序
        process(arr, 0, arr.length - 1);
    }

    private void process(int[] arr, int L, int R) {

        //分治
        //分成左右两个数组 分别排序 然后合并
        int mid = (L + R) / 2;
        process(arr, L, mid);
        process(arr, mid + 1, R);
        //排好序后合并
        merge(arr, L, mid, R);
    }

    private void merge(int[] arr, int L, int mid, int R) {
        //双指针合并

        int p1 = L;
        int p2 = mid + 1;
        //申请一个帮助数组 哪个指针的数大 拷贝哪个指针的数到新数组中
        int[] helpArr = new int[R - L + 1];
        int i = 0;
        while (p1 <= mid && p2 <= R) {
            if (arr[p1] <= arr[p2]) {
                helpArr[i] = arr[p1];
                p1++;
            } else {
                helpArr[i] = arr[p2];
                p2++;
            }
            i++;
        }

        //跳出循环后 要么是p1越界 要么是 p2越界
        while (p1 <= mid) {
            helpArr[i++] = arr[p1++];
        }
        while (p2 <= R) {
            helpArr[i++] = arr[p2++];
        }

        //将help数组拷贝回 原数组
        for (int j = 0; j < helpArr.length; j++) {
            arr[L + j] = helpArr[j];
        }
    }


}
